package Sort2;

import java.util.Arrays;

public class Heap {
    public static void main(String[] args) {
        int[] arr = {5, 9, 8, 1, 1, 5,4,6,7,8,5, 4};
        heap(arr);
        System.out.println(Arrays.toString(arr));
    }

    public static void heap(int[] arr) {
        creat(arr);
        int size = arr.length - 1;
        for (int i = 0; i < arr.length; i++) {
            int temp = arr[size];
            arr[size] = arr[0];
            arr[0] = temp;
            size--;
            down(0, arr, size);
        }
    }

    public static void creat(int[] arr) {
        for (int i = (arr.length - 2) / 2; i >= 0; i--) {
            down(i, arr, arr.length - 1);
        }
    }

    public static void down(int index, int[] arr, int size) {
        int parent = index;
        int child = parent * 2 + 1;
        while (child <= size) {
            if (child + 1 <= size) {
                int temp = arr[child + 1];
                if (temp > arr[child]) {
                    child++;
                }
            }
            if(arr[child]>arr[parent]) {
                int temp = arr[parent];
                arr[parent] = arr[child];
                arr[child] = temp;
            }
            parent = child;
            child = parent * 2 + 1;
        }

    }
}
